1. Field
The following description relates to a method and apparatus for managing a stack, and more particularly, to a method and apparatus for managing a stack used for a tree traversal (TRV).
2. Description of the Related Art
Three dimensional (3D) rendering may refer to an image processing procedure that synthesizes data of a 3D object into an image visible from a view point of a camera provided.
A rendering scheme may include a rasterization scheme and a ray tracing scheme. The rasterization scheme may generate an image by projecting a 3D object onto a screen. The ray tracing scheme may generate an image by tracing a path of incident light along a ray transmitted toward a respective pixel of the image from the view point of the camera.
The ray tracing scheme may be advantageous in that a high quality image may be generated based on a physical property of light, such as reflection, refraction, transmission, and the like. However, the ray tracing scheme may face a difficulty in processing rendering at a high speed because a substantial amount of calculation is used for the ray tracing.
One factor used to determine a performance of the ray tracing may include a traversal (TRV) of an acceleration structure (AS) and an intersection test (IST) between ray-primitives. The TRV of the AS and the IST between the ray-primitives may be performed tens of times with respect to a plurality of rays.
The AS may be a partitioning AS. The AS may be a data structure in which scene objects to be rendered are represented through being partitioned spatially. A material structure, such as a grid, a k-dimensional (k-d) tree, a bounding volume hierarchy (BVH), and the like, may be used as the AS.
Processing the ray tracing with respect to a signal ray may not be dependent on processing the ray tracing with respect to another ray. Accordingly, ray traversing hardware of a multiple instruction multiple data (MIMD) architecture may process multiple ray TRVs in parallel. When a ray TRV is processed by an acceleration of hardware, a pipeline architecture and a multi-core structure may enhance a performance of the ray TRV.
When a number of rays being processed simultaneously increases, a number of registers to be maintained for the ray tracing may increase. Also, a storage space for managing a stack used for the ray tracing may occupy a large portion of storage space in the ray traversing hardware.